package com.base.leetcode;

import com.base.dataStructure.heap.MinHeap;

/**
 * @Author: hdhao
 * @Create: 2023/3/30 - 20:39
 * @Version: v1.0
 */
//合并多个有序链表
public class Leetcode23 {

    public static ListNode mergeLists(ListNode[] lists){
        if (lists.length == 0){
            return null;
        }
        return split(lists,0,lists.length-1);
    }
    //返回合并后的链表,i,j代表左右边界
    private static ListNode split(ListNode[] lists, int i,int j){
        if (i == j){
            //数组内只有一个链表
            return lists[i];
        }
        int m = (i+j) >>> 1;
        ListNode left = split(lists, i, m);
        ListNode right = split(lists, m + 1, j);
        return mergeTwoLists(left,right);
    }

    public static ListNode mergeTwoLists(ListNode p1,ListNode p2){
        //新链表的哨兵节点
        ListNode s = new ListNode(-1,null);
        //新链表指针变量
        ListNode p = s;
        //当p1和p2 有一个为null时，退出循环，将两一个链表剩下的节点全部链接到新链表
        while (p1!=null && p2!=null){
            //将p1 和 p2 中较小的值链接到新链表后边
            if (p1.val < p2.val){
                p.next = p1;
                p1 = p1.next;
            }else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1!=null){
            p.next = p1;
        }
        if (p2 !=null){
            p.next = p2;
        }
        return s.next;
    }

    //合并多个有序数组
    public ListNode mergeKLists(ListNode[] lists) {
        MinHeap heap = new MinHeap(lists.length);
        //将链表的头结点加入到小顶堆
        for (ListNode h : lists) {
            if (h != null){
                heap.offer(h);
            }
        }
        ListNode s = new ListNode(-1, null);
        ListNode t = s;
        while (!heap.isEmpty()){
            ListNode min = heap.poll();
            t.next = min;
            t = min;
            if (min.next != null) {
                heap.offer(min.next);
            }
        }
        return s.next;
    }
}
